0%

Self-Learned Algorithms - 02

Posted on In

Self-Learned Algorithms - 02

This is my learning note about algorithms.

Reference

19.删除链表倒数第N个节点

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

题解

  • 哨兵节点的应用：一个附加在原链表最前面用来简化边界条件的附加节点，它的值域不存储任何东西，只是为了操作方便而引入。
  • 要求一次遍历？那么就不存在第一次遍历找到链表长度，然后第二次遍历找到该节点。

解法

  • 双指针
1
2
3
4
5
6
7
8
9
10
Node = ListNode(None)
Node.next = head
fast,slow = Node,Node
for i in range(n):
	fast = fast.next
while fast.next != None:
	fast = fast.next
	slow = slow.next
slow.next = slow.next.next
return Node.next
  • 递归
1
2
3
4
5
6
7
global i 
if head is None:
  i=0
  return None
head.next = self.removeNthFromEnd(head.next,n)
i+=1
return head.next if i==n else head

递归的好处在于无论删除哪一个节点都可以返回正确的节点。（那么除了利用global i是否还有其他方法可以处理递归的次数呢，比如直接处理n？）

（递归的内存消耗比双指针稍高）

21.合并两个有序链表

https://leetcode-cn.com/problems/merge-two-sorted-lists

题解

  • 设置一个哨兵节点，然后指向两个剩余链表中较小的一个

解法

  • 双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
pre = ListNode(None)
node = pre
while l1 and l2:
  if l1.val < l2.val:
    node.next, l1 = l1, l1.next
  else:
    node.next, l2 = l2, l2.next
  node = node.next
if l1:
	node.next = l1
else:
	node.next = l2
return pre.next
  • 递归法
1
2
3
4
if l1 and l2:
  if l1.val > l2.val: l1, l2 = l2, l1
  l1.next = self.mergeTwoLists(l1.next, l2)
return l1 or l2

最后的return l1 or l2是防止l1为空、l2不为空时输出为空的情况发生。

备注：

在 Python 中，and和 or都有提前截至运算的功能。

and：如果and前面的表达式已经为False，那么and之后的表达式将被 跳过，返回左表达式结果
or：如果or前面的表达式已经为True，那么or之后的表达式将被跳过，直接返回左表达式的结果
例子：[] and 7 等于 []

141.环形链表

https://leetcode-cn.com/problems/linked-list-cycle

题解

  • 题目看起来很简单，但是中文版的描述也讲了很多无关紧要的东西，所以评论区才会出现各种奇奇怪怪的解法（？）

解法

  • 哈希表：记录访问过的位置
1
2
3
4
5
6
7
8
9
dic = {}
node = head
while(node):
  if(dic.get(node,0) != 0):
  	return True
  else:
  	dic[node] = 1
  node = node.next
return False
  • 列表：利用列表寻找是否存在重复的对象
1
2
3
4
5
6
7
8
9
if not head:
	return head
m = []
while head:
  if head in m:
  	return True
  m.append(head)
  head = head.next
return False
  • 双指针：定义一个快指针和慢指针,每次快指针走2步，慢指针走1步，判断快指针是否与慢指针重逢。可以有效的减少空间复杂度和时间复杂度的匹配次数
1
2
3
4
5
6
7
8
9
10
11
slow = fast = head
# if not head：  # 没必要这样写可以加入while循环判断更简洁
#     return False

while fast and fast.next:  # 防止head为空和出现空指针的next的情况
  slow = slow.next
  fast = fast.next.next
  if slow is fast:
    return True

return False
  • 奇奇怪怪的神仙解法（不能学习）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 把访问过的值都进行赋值，如果链表完全成环，则必会出现重复值
while head:
  if head.val == 'bjfuvth': #其实什么字符都可以，越奇葩越好
  	return True
  else:
  	head.val = 'bjfuvth'
  head = head.next
return False

# 或者递归也可以
if not head:
  return False

if head == 0xcafebabe:
  return True

head.val = 0xcafebabe
return self.hasCycle(head.next)